package 子数组问题;

/**
 * @Date 2024/6/11 20:41
 * @description: 乘积为正数的最长子数组长度
 * .            https://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/description/
 * @Author LittleNight
 */
public class likou1567 {

    // 状态方程看视频详解
    public int getMaxLen(int[] nums) {
        int n = nums.length;
        int[] f = new int[n + 1]; //表示以i位置为结尾的所有子数组乘积为正数的最大长度
        int[] g = new int[n + 1]; //以i位置为结尾的所有子数组乘积为负数的最小长度 (详解看视频)
        f[0] = 0;
        g[0] = 0; // 注意这个题比之前的最大子数组和不同, 那次我们没有添加虚拟节点, 此处我们新加了一个格子, 所以要进行初始化确保后面的值是对的

        int ret = -0x3f3f3f3f;
        // 注意这里是多加了一个数组格子, 所以要注意和nums[i]的下标映射
        for (int i = 1; i < n + 1; i++) {
            int x = nums[i - 1];
            if(x > 0) {
                f[i] = Math.max(f[i - 1] + 1, 1); // 其实不用写1,因为如果f=0 加1之后还是1
                g[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
            } else if(x < 0) {
                f[i] = g[i - 1] == 0 ? 0 : g[i - 1] + 1;
                g[i] = f[i - 1] + 1; // 找前面是正数的
            }

            // 边遍历边更新, dp[0] 是虚拟节点, 不是我们要的答案
            ret = Math.max(ret, f[i]);
        }
        return ret;
    }


}
